Papers^γ

### Nice and promising heuristic for large and sparse SDP "we present computational results which show that the method finds optimal solutions to (2) quite reliably, and although we are able to derive some amount of theoretical justification for this, our belief that the method is not strongly affected by the inherent nonconvexity of (2) is largely experimental" ### Optimality I read: "Theorem 2.2. There exists an optimal solution $X^∗$ of (1) with rank r satisfying the inequality $r(r+ 1)/2 ≤ m$.", where (1) is the standard-form primal SDP and $m$ is the number of linear constraints in the SDP. Is there a proof that with $r>\sqrt{2m}$, SDPLR gives the optimal solution? i.e. any local minimum is a global minimum? ### Goemans-Williamson SDP relaxation This is an algorithm that seems more scalable: https://github.com/maxdan94/spingraphSDP

Survey paper: [Low-Rank Semidefinite Programming: Theory and Applications](http://www1.se.cuhk.edu.hk/~manchoso/papers/low_rank-FnT_Opt.pdf)